/**
 * Luogu 2886
 *
 * 加操作：min
 * 乘操作：+
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef vector<int> vi;
const int V = 205;
const int INF = 0x3f3f3f3f;
struct Mat {
  int r, c;
  vector<vi> f;
  Mat() : r(V), c(V), f(V + 1, vi(V + 1)) {
    // 每一个矩阵，初始化为 加操作 的幺元
    for (int i = 0; i <= V; ++i)
      for (int j = 0; j <= V; ++j) f[i][j] = INF;
  }
  Mat operator*(const Mat& b) const {
    Mat m;
    for (int i = 0; i <= m.r; ++i)
      for (int j = 0; j <= m.c; ++j)
        for (int k = 0; k <= m.c; ++k) {
          // 如果是矩阵乘加会写为 m.f[i][j] = m.f[i][j] + a.f[i][k] * b.f[k][j]
          // 先乘后加萌萌哒！（忽然
          m.f[i][j] = min(m.f[i][j], f[i][k] + b.f[k][j]);
        }
    return m;
  }

  // 幂运算没啥好说的，和乘加一样
  Mat operator^(LL x) const {
    assert(r == c);
    Mat m = *this, p = *this;
    for (--x; x; x >>= 1, p = p * p)
      if (x & 1) m = m * p;
    return m;
  }
} G, Ans;
map<int, int> ID;
int sz;
// 图足够稀疏，离散化
int getID(int u) {
  if (!ID.count(u)) ID[u] = sz++;
  return ID[u];
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int n, t, s, e;
  cin >> n >> t >> s >> e;
  sz = 0;

  for (int i = 1; i <= t; ++i) {
    int w, u, v;
    cin >> w >> u >> v;
    u = getID(u), v = getID(v);
    G.f[u][v] = G.f[v][u] = min(G.f[u][v], w);
  }
  Ans = G ^ n;
  printf("%d\n", Ans.f[getID(s)][getID(e)]);
}
